package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/10/20 14:22
 * @Describe
 */

public class QuickSortFindKthLargest {
    int[] arr;

    /**
     * 使用快速排序算法查找数组中第K大的元素
     *
     * @param arr 待排序的数组
     * @param k   要找的第K大元素的索引（从1开始）
     * @return 第K大的元素
     * @throws IllegalArgumentException 如果输入数组为空、k的值为非正数或超过数组长度，则抛出此异常
     */
    public int findKthLargest(int[] arr, int k) {
        // 检查输入数组和k的值是否有效
        if (arr == null || arr.length == 0 || k <= 0 || k > arr.length) {
            throw new IllegalArgumentException("Invalid Input.");
        }
        // 将输入数组赋值给类的成员变量
        this.arr = arr;
        // 调用深度优先搜索方法来排序数组，以找到第K大的元素
        dfs(0, arr.length - 1, arr.length - k);
        // 返回第K大的元素
        return arr[arr.length - k];
    }

    /**
     * 使用深度优先搜索（DFS）来找到数组中第K大的元素
     * 该方法基于快速选择算法，通过递归地划分数组来定位第K大的元素
     *
     * @param left  左边界，表示当前处理区间的左端点
     * @param right 右边界，表示当前处理区间的右端点
     * @param k     目标位置，表示要寻找的第K大的元素的位置
     */
    private void dfs(int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(left, right);
        // 根据pivot的位置与k的大小关系，决定是向左子区间还是右子区间搜索
        if (pivotIndex < k) {
            dfs(pivotIndex + 1, right, k);
        } else if (pivotIndex > k) {
            dfs(left, pivotIndex - 1, k);
        }
    }

    /**
     * 快速排序的分区操作
     *
     * @param left  左边界
     * @param right 右边界
     * @return 分区后的基准元素索引
     */
    private int partition(int left, int right) {
        // 选择右侧元素作为基准值
        int pivot = arr[right];
        // 初始化左指针
        int i = left;
        // 初始化右指针，从右侧第二个元素开始
        int j = right - 1;

        // 当左指针小于右指针时，进行循环
        while (i < j) {
            // 移动左指针，直到找到大于基准值的元素
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            // 移动右指针，直到找到小于基准值的元素
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            // 如果左指针仍然小于右指针，交换两者指向的元素
            if (i < j) {
                swap(i, j);
            }
        }
        // 最后，将基准值与左指针指向的元素交换，确保基准值位于中间
        swap(i, right);
        // 返回基准值的索引
        return i;
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private void swap(int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 4};
        QuickSortFindKthLargest quickSort = new QuickSortFindKthLargest();
        int k = 2; // 寻找第2大的数
        int result = quickSort.findKthLargest(arr, k);
        System.out.println("The " + k + "th largest number is: " + result);
    }
}


